Routers and switches are network devices that determine which communication link or links to employ to support the progress of data packets through the network. A network node that determines which links to employ based on information in the network (OSI layer 3) is called a router. Link state routing protocols such as Border Gateway Protocols (“BGP”) and Interior Gateway Protocols (“IGP”) enable each router to understand which other router is the “next hop” that a packet should take towards its destination. One example of an IGP is the Open Shortest Path First Protocol (“OSPF”). Routers use the routing protocols to construct routing tables. Thereafter, when a router receives a data packet and has to make a forwarding decision, the router locates the next hop in the routing table. Conventionally, the routers look up the routing table using the destination IP address provided in the data packet as an index.
OSPF and similar link state routing protocols use a Hello protocol (e.g., the OSPF Hello protocol) to acquire neighbors, which are other routers with interfaces to a common network. The router sends Hello packets to its neighbors and receives their hello packets. In addition to helping acquire neighbors, Hello packets also act as “keepalives,” which are messages that let routers know that other routers are still functional. On multi-access networks (networks supporting more than two routers), the Hello protocol elects a designated router and a backup designated router. When the topological databases of two neighboring routers are synchronized, the routers are said to be adjacent or collectively form an adjacency. Adjacencies control the distribution of routing-protocol packets, which are sent and received only on adjacencies. In particular, link state messages such as Link State advertisements (LSAs) are exchanged among adjacent routers to communicate routing and topology information. Each router periodically sends its LSAs to provide information on the router's adjacencies or to inform others when a router's state changes. By comparing established adjacencies to link states, failed routers can be detected quickly, and the network's topology can be altered appropriately.
The infrastructure of a router typically comprises functional components organized as a control plane and a data plane. The control plane includes the functional components needed to manage the traffic forwarding features of the router. These components include routing protocols, configuration information and other similar functions that determine the destinations of data packets based on information other than that contained within the packets. The data plane, on the other hand, includes functional components needed to perform forwarding operations for the packets.
The control plane generally tends to be more complex than the data plane in terms of the quality and quantity of software operating on the supervisor processor. Therefore, failures are more likely to occur in the control processor when executing such complicated code. In order to ensure high availability in a router, it is desirable to configure the router such that if a failure arises with the control plane that requires restarting of software executing on the control processor, the data plane continues to operate correctly. Restarting of control plane software may be necessary because of a failure with a routing protocol component or a software upgrade to that component. A router that is configured to enable its data plane to continue packet forwarding operations during restart of the control plane software is referred to as a non-stop forwarding (NSF) capable router.
Situations where a NSF capable router architecture is useful include both anticipated and non-anticipated failures in the control plane of the router. For example, failures in the control plane can include unanticipated or unplanned events (e.g., software crashes or hardware errors) as well as planned or anticipated events (e.g., scheduled maintenance). As for the latter, it may be desired to upgrade software running on the control processor or even remove and replace that processor for service. Such an upgrade or removal/replacement may cause an interruption in one or more routing protocols, but the NSF nature of the router allows continued forwarding of data through the router.
NSF router architectures have been implemented to enhance router availability and avoid disruption of data connectivity. These previous implementations often require modifications to routing protocols such as OSPF to add support for NSF and related processes. For example, modifications to the OSPF routing protocol allow support for a so-called graceful restart after a link state router protocol failure. When the router is restarted, the modified protocol allows the router to obtain information via protocol message exchanges with its neighbors and without the neighbors “viewing” the router as being completely down, thereby obviating any changes to the routing topology.
Unfortunately, conventional graceful restart processes require both the failed router and its neighbors to support graceful restart extensions or enhancements to the link state routing protocol. However, not all routers support such routing protocol extensions. Accordingly, it would be desirable to perform a graceful restart in a simple manner without the need to extend the link state routing protocol.